package linked;

import java.util.ArrayList;

public class NodeTest {
        // 单向链表
        public static class Node {
            int value;
            Node next;

            public Node(int value) {
                this.value = value;
            }
        }

        /*
        * 判断单链表是否有回文，基于快慢指针法  额外空间复杂度为O(1)
        * */
        public static boolean chkPalindrome(Node A) {
            boolean resule=false;
            // write code here
            //如果为空 返回true
            if(A.next == null){
                return true;
            }
            Node fastPoint=A;
            Node slowPoint=A;
            int nodeSize=0;  //定义链表长度
            while (fastPoint.next != null){
                fastPoint=fastPoint.next;
                nodeSize++;
                if (fastPoint.next !=null){
                fastPoint=fastPoint.next;
                slowPoint=slowPoint.next;
                nodeSize++;
                }
            }
            //将链表从慢指针开始的下一个节点开始全部逆序
            Node pre = reverseList(slowPoint.next);
            while (pre!=null && A!=null){
                if (pre.value==A.value){
                    resule=true;
                    pre=pre.next;
                    A=A.next;
                }else {
                    resule=false;
                    break;
                }
            }
            return  resule;
    }


    // 反转单向链表
    public static Node reverseList(Node head) {
        Node next = null;
        Node pre = null;
        while (head != null) {
            next = head.next;// 备份
            head.next = pre;// 将头节点的下一个节点指向空（pre）
            pre = head;// pre指向原来的头节点
            head = next;// 头节点变为了它的下一节点（向下移动了一位）
        }
        return pre;// 因为head是在为空的时候退出的循环，所以应该返回他的上一节点
    }






    /*
    * 将指定链表逆序指定长度, 返回的节点是逆序后的链表的新头节点
    * */
    public static Node reverNode(Node head,int size){
        Node temp=null;
        Node pre=null;
        while (head.next!=null){
            temp=head.next;
            head.next=pre;
            pre=head;
            head=temp;
        }
        return pre;
    }



        //判断一个链表是否为回文结构  | 基于数组   需要额外O(n)的空间复杂度
        public static boolean isSym(Node head){
            int nodeSize=0;   //链表长度
            ArrayList<Node> nodeArrayList=new ArrayList<>();
            Node tempHead=head;
            while (head !=null){
                nodeArrayList.add(head);
                nodeSize++;
                head=head.next;
            }
            System.out.print(nodeArrayList.size()+" " +nodeSize);
            for (int i=nodeSize-1 ; i>=0;i--){
                System.out.println(tempHead.value+"||"+nodeArrayList.get(i).value);
                if (tempHead.value != nodeArrayList.get(i).value){
                    return false;
                }
                tempHead=tempHead.next;
            }
            return true;
        }







        // 打印单向链表
        public static void printList(Node head) {
            System.out.print("Linked List:");
            while (head != null) {
                System.out.print(head.value + " ");
                head = head.next;
            }
            System.out.println();
        }

/////////////////////////////////////////////////////////////

        // 双向链表
        public static class DoubleNode {
            int value;
            DoubleNode last;
            DoubleNode next;

            public DoubleNode(int value) {
                this.value = value;
            }
        }
        // 反转双向链表
        public static DoubleNode reverseList(DoubleNode head) {
            DoubleNode pre = null;
            DoubleNode next = null;
            while (head != null) {
                next = head.next;
                head.next = pre;
                head.last = next;
                pre = head;
                head = next;
            }
            return pre;
        }

        // 打印双向链表
        // 分正向和反向打印！！
        public static void printList(DoubleNode head) {
            System.out.print("Double Linked List: ");
            DoubleNode end = null;
            while (head != null) {
                System.out.print(head.value + " ");
                end = head;
                head = head.next;
            }
            System.out.print(" ||  ");
            while (end != null) {
                System.out.print(end.value + " ");
                end = end.last;
            }
            System.out.println();
        }

        public static void main(String[] args) {
            Node head1 = new Node(1);
            head1.next = new Node(2);
            head1.next.next = new Node(3);
            printList(head1);
            head1 = reverseList(head1);
            printList(head1);

            System.out.println("==================");

            DoubleNode head2 = new DoubleNode(1);
            head2.next = new DoubleNode(2);
            head2.next.last = head2;
            head2.next.next = new DoubleNode(3);
            head2.next.next.last = head2.next;
            head2.next.next.next = new DoubleNode(4);
            head2.next.next.next.last = head2.next.next;
            printList(head2);
            printList(reverseList(head2));
        }
    }
